# This is an implementation of insertion sort.

import random

_SAMPLE_VALUES = 1000
_SAMPLE_COUNT = 100

def main():
  values = random.sample(xrange(_SAMPLE_VALUES), _SAMPLE_COUNT)

  print 'unsorted values', values

  for j in xrange(1, len(values)):
    key = values[j]
    # Insert values[j] into the sorted sequence values[1..j -1].
    i = j - 1
    while i >= 0 and values[i] > key:
      values[i+1] = values[i]
      i = i - 1
    values[i+1] = key

  print 'sorted values', values
  
if __name__ == "__main__":
    main()
    
